package com.ShangGuiGu.sortAlgorithm.交换排序.插入排序;

/**
 * @auther zsj
 * @Date 2022/2/17
 *
 * 插入排序
 *
 * 选择数组的第一个数字作为一个有序列，然后把后面的数字作为无序列
 * 大于放在前，小于放在后 组成一个新序列
 * （注意加条件使数字放在合适位置）
 **/
public class InsertSort {
    public static void main(String[] args) {

        int arr[] ={101,34,56,24,-1,15};
        int[] ints = insertSort(arr);
        for (int anInt : ints) {
            System.out.println(anInt);
        }

    }

    /**
     * 方法
     * @param n
     * @return
     */
    static int[] insertSort(int[] n){

        //  101 25 36 44
         for (int i = 1; i < n.length; i++) {
            int insertVal=n[i];//待插入的数字
            int insertIndex=i-1;//待插入的下标
            while (insertIndex >= 0 && insertVal < n[insertIndex] ){
                //到这里就说明，待插入的数字并没有到达他该有的位置，我们就将当前的数字后移一位
                //并且将待插入的数字赋值到原来的数字位置
                n[insertIndex + 1] = n[insertIndex];
                n[insertIndex] =insertVal;//将存储的值赋值回该有的位置，这里可以优化加个判断，但是,不是很有必要
                insertIndex--;//退出循环的条件,将小的数字往后调
            }
        }
        return n;
    }
}
